package com.fps.webshop.question.question0600_0699;

import java.util.HashSet;

import com.fps.webshop.question.common.TreeNode;

/**
 * 653. 两数之和 IV - 输入 BST
 * 
 * 给定一个二叉搜索树 root 和一个目标结果 k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
 * 
 * 示例 1：
 * Question653_01.jpg
 * 输入: root = [5,3,6,2,4,null,7], k = 9
 * 输出: true
 * 
 * 示例 2：
 * Question653_02.jpg
 * 输入: root = [5,3,6,2,4,null,7], k = 28
 * 输出: false
 * 
 * 示例 3：
 * 输入: root = [2,1,3], k = 4
 * 输出: true
 * 
 * 示例 4：
 * 输入: root = [2,1,3], k = 1
 * 输出: false
 * 
 * 示例 5：
 * 输入: root = [2,1,3], k = 3
 * 输出: true
 *  
 * 提示:
 * 二叉树的节点个数的范围是  [1, 104].
 * 		-10^4 <= Node.val <= 10^4
 * 		root 为二叉搜索树
 * 		-10^5 <= k <= 10^5
 */
public class Question653 {
	
	/**
	 * 第一次提交，二叉树遍历+HashSet
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		3 ms	39.2 MB	Java	2021/08/24 15:59
	 * 
	 * 执行用时：3 ms, 在所有 Java 提交中击败了84.45%的用户
	 * 内存消耗：39.2 MB, 在所有 Java 提交中击败了75.88%的用户
	 */
	public static boolean findTarget(TreeNode root, int k) {
	    HashSet<Integer> hashset = new HashSet<Integer>();
	    return preOrder(root,hashset,k);     
	}
	public static boolean preOrder(TreeNode root,HashSet<Integer> hashset,int k){
	    if(root == null)
	        return false;
	    if(hashset.contains(k - root.val)){
	        return true;
	    }
	    hashset.add(root.val);        
	    return preOrder(root.left,hashset,k) || preOrder(root.right,hashset,k);
	}

	public static void main(String[] args) {
		TreeNode root = new TreeNode(51);
		TreeNode leftNode1 = new TreeNode(4);
		TreeNode rightNode1 = new TreeNode(6);
		root.left = leftNode1;
		root.right = rightNode1;
		
		//TreeNode rightNode2 = new TreeNode(67);
		//leftNode1.right = rightNode2;
		
		TreeNode leftNode3 = new TreeNode(3);
		TreeNode rightNode3 = new TreeNode(7);
		rightNode1.left = leftNode3;
		rightNode1.right = rightNode3;
		
		System.out.print(findTarget(root,7));
		
	}
}
